package cn.jdemo.algorithm.demo;

import java.util.Arrays;
// 快排
public class Demo02 {
    public static void main(String[] args) {
        quickSort();
    }

    public static void quickSort(){
        int[] arrs = new int[]{1,2,3,6,4,5,7,8,9,10,10};
        doQuickSort(arrs,0, arrs.length-1);
        System.out.println(Arrays.toString(arrs));
    }
    public static void doQuickSort(int[] arrs,int left, int right){
        if (left >= right ){return;}
        int parttion = getParttion(arrs,left,right);
        doQuickSort(arrs,left,parttion-1);
        doQuickSort(arrs,parttion+1,right);
    }

    private static int getParttion(int[] arrs, int left, int right) {
        int pivotVal = arrs[left];
        int idx = left+1;
        for(int i=idx; i<=right;i++){
            if (arrs[i] > pivotVal){
                swap(arrs,i,idx);
                idx++;
            }
        }
        swap(arrs,left,idx-1);
        return idx-1;
    }

    private static void swap(int[] arrs, int x, int y) {
        if (x == y){
            return;
        }
        arrs[x] = arrs[x] ^ arrs[y];
        arrs[y] = arrs[x] ^ arrs[y];
        arrs[x] = arrs[x] ^ arrs[y];
    }
}
